0845. 数组中的最长山脉【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双指针

1. 📝 题目描述

• leetcode

把符合下列属性的数组 arr 称为 山脉数组 ：

• arr.length >= 3
• 存在下标 i（0 < i < arr.length - 1），满足
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

给出一个整数数组 arr，返回最长山脉子数组的长度。如果不存在山脉子数组，返回 0。

---

示例 1：

输入：arr = [2,1,4,7,3,2,5]
输出：5
解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。

示例 2：

输入：arr = [2,2,2]
输出：0
解释：不存在山脉子数组。

---

提示：

• 1 <= arr.length <= 10^4
• 0 <= arr[i] <= 10^4

进阶：

• 你可以仅用一趟扫描解决此问题吗？
• 你可以用 O(1) 空间解决此问题吗？

2. 🎯 s.1 - 双指针

c

int longestMountain(int* arr, int arrSize) {
    int res = 0, i = 1;
    while (i < arrSize) {
        while (i < arrSize && arr[i] <= arr[i-1]) i++;
        int up = 0;
        while (i < arrSize && arr[i] > arr[i-1]) { up++; i++; }
        int down = 0;
        while (i < arrSize && arr[i] < arr[i-1]) { down++; i++; }
        if (up > 0 && down > 0 && up + down + 1 > res) res = up + down + 1;
    }
    return res;
}

js

/**
 * @param {number[]} arr
 * @return {number}
 */
var longestMountain = function (arr) {
  const n = arr.length
  let res = 0,
    i = 1
  while (i < n) {
    while (i < n && arr[i] <= arr[i - 1]) i++
    let up = 0
    while (i < n && arr[i] > arr[i - 1]) {
      up++
      i++
    }
    let down = 0
    while (i < n && arr[i] < arr[i - 1]) {
      down++
      i++
    }
    if (up > 0 && down > 0) res = Math.max(res, up + down + 1)
  }
  return res
}

py

class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        n = len(arr)
        res = 0
        i = 1
        while i < n:
            while i < n and arr[i] <= arr[i - 1]:
                i += 1
            up = 0
            while i < n and arr[i] > arr[i - 1]:
                up += 1
                i += 1
            down = 0
            while i < n and arr[i] < arr[i - 1]:
                down += 1
                i += 1
            if up > 0 and down > 0:
                res = max(res, up + down + 1)
        return res

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(1)$

算法思路：

• 跟踪上升段和下降段的长度，当两者都 > 0 时构成山脉
• 一次遍历即可找到最长山脉